package offer.offer02;



import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 就层序遍历二叉树
 * 试一试LinkedList或者deque, 因为他是正反两个方向的迭代。别人的解法, 其实差不太多。
 */
public class S32III从上到下打印二叉树 {
    /**
     * 99, 没想到性能还可以。就和S32II一样, 但是在处理结束之后对偶数层做了一个交换
     * nodeList1和nodeList2改成LinkedList后时间增加。看来ArrayList做随机访问性能确实还行。
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) return new LinkedList<>();
        List<List<Integer>> res = new LinkedList<>();
        List<TreeNode> nodeList1 = new ArrayList<>();
        List<TreeNode> nodeList2 = new ArrayList<>();
        nodeList1.add(root);
        while(nodeList1.size() != 0){
            List<Integer> resEle = new ArrayList<>();
            for(TreeNode tempNode: nodeList1){
                resEle.add(tempNode.val);
                if(tempNode.left != null) nodeList2.add(tempNode.left);
                if(tempNode.right != null) nodeList2.add(tempNode.right);
            }
            res.add(resEle);
            nodeList1 = nodeList2;
            nodeList2 = new ArrayList<>();
        }
        boolean flag = false;
        for(List<Integer> tempRes: res){
            if(flag) swap(tempRes);
            flag = !flag;
        }
        return res;
    }
    public void swap(List<Integer> inputList){
        int size = inputList.size();
        for(int i = 0; i < size / 2; i++){
            Integer temp1 = inputList.get(i);
            // inputList.get(i) = inputList.get(size - 1 - i);
            inputList.set(i, inputList.get(size - 1 - i));
            inputList.set(size - 1 - i, temp1);
        }
    }

}
